#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣343. 整数拆分
// 【难度】中等
// 【提交】2025.10.21 https://leetcode.cn/problems/integer-break/submissions/672444548/
// 【提交】2025.10.21 https://leetcode.cn/problems/integer-break/submissions/672440751/
// 【标签】数学；动态规划
class Solution_LC0343 {
public:
    int integerBreak(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        int res = 1;
        while(n > 4) {
            res *= 3;
            n -= 3;
        }
        res *= n;
        return res;
    }
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for(int i = 3; i <= n; ++i) {
            for(int j = 1; j < i - 1; ++j) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个正整数n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。
 * 返回可以获得的最大乘积。
 * 
 * 二、两种解法对比
 * 
 * 解法1：数学解法（贪心）
 * 核心思想：尽可能多地拆分出3，当剩余4时拆分为2+2
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 * 优点：效率高，代码简洁
 * 缺点：需要数学证明，理解难度较大
 * 
 * 解法2：动态规划
 * 状态定义：dp[i]表示将整数i拆分后得到的最大乘积
 * 状态转移：dp[i] = max(dp[i], max((i-j)*j, dp[i-j]*j))
 * 时间复杂度：O(n²)
 * 空间复杂度：O(n)
 * 优点：思路直观，易于理解
 * 缺点：效率较低，需要额外空间
 * 
 * 三、数学原理证明
 * 1. 任何大于4的数都可以拆分成3和更小的数
 * 2. 当n=2时，最大乘积为1（1×1）
 * 3. 当n=3时，最大乘积为2（1×2）
 * 4. 当n=4时，拆分为2+2（乘积4）优于3+1（乘积3）
 * 5. 当n>4时，拆出3总是比拆出2能得到更大的乘积
 * 
 * 四、复杂度分析
 * 数学解法：时间O(n)，空间O(1)
 * 动态规划：时间O(n²)，空间O(n)
 * 
 * 五、应用场景
 * 数学解法：适合对性能要求高的场景
 * 动态规划：适合教学和理解问题本质
 * 
 * 六、一句话总结
 * 数学解法高效但需要证明，动态规划直观但效率较低，根据场景选择合适的解法。
 */